package com.lsa.helpers.tree.binary;

import java.util.AbstractMap;
import java.util.AbstractMap.SimpleEntry;
import java.util.Map;

import com.lsa.helpers.Pair;

public abstract class BinaryTreeUtils {
	public static <T> Pair<Boolean, IBinaryTreeNode<T>> isBinaryTree(IBinaryTreeNode<T> root, INumberConverter<T> numberConverter){
		return isBinaryTreeInner(root, numberConverter, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
	}
	
	private static <T> Pair<Boolean, IBinaryTreeNode<T>> isBinaryTreeInner(IBinaryTreeNode<T> root, INumberConverter<T> numberConverter, double min, double max){
		if (root == null) return createPair(true, null);
		Number nodeValue = numberConverter.convert(root.getData());
		boolean isBinaryTree = nodeValue.doubleValue() > min && nodeValue.doubleValue() < max;
		if (!isBinaryTree){
			return createPair(false, root);
		}
		
		Pair<Boolean, IBinaryTreeNode<T>> leftTreeResult = isBinaryTreeInner(root.getLeftSubtree(), numberConverter, min, nodeValue.doubleValue());
		if (!leftTreeResult.getFirst()){
			return leftTreeResult;
		}
		
		Pair<Boolean, IBinaryTreeNode<T>> rightTreeResult = isBinaryTreeInner(root.getRightSubtree(), numberConverter, nodeValue.doubleValue(), max);
		if (!rightTreeResult.getFirst()){
			return rightTreeResult;
		}
		
		return createPair(true, null);
	}

	private static <T> Pair<Boolean, IBinaryTreeNode<T>> createPair(boolean first, IBinaryTreeNode<T> second) {
		return new Pair<Boolean, IBinaryTreeNode<T>>(first, second);
	}
}
